#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
// 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
// 两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

// 例子：
// 输入：s = "loveleetcode", c = "e"
// 输出：[3,2,1,0,1,0,0,1,2,2,1,0]
#define MIN(A,B) ((A)<(B)? (A):(B))

int* shortestToChar(char * s, char c, int* returnSize){
    int i, len = strlen(s);

    int *res = calloc(len, sizeof(int));    //初始化为0  

    //找到字符左右边界，初始化边界外的字符
    int l = 0, r = len-1;
    while (s[l] != c) l++;
    while (s[r] != c) r--;  //注意自增运算符号
    for (i = 0; i < l; i++) res[i] = l-i;
    for (i = len-1; i > r; i--) res[i] = i-r;


    // 以左边目标为参照，计算距离
    int left_idx = l; 
    for (i = l+1; i < r; i++) {
        if (s[i] == c) {    //
            left_idx = i;
            continue;
        } else
            res[i] = i - left_idx; 
    }

    // 以右边目标为参照，计算距离
    int *tmp[len];
    int right_idx = r;
    for (i = r-1; i > l; i--) {
        if (s[i] == c) {
            right_idx = i;
            continue;
        } else 
            tmp[i] = right_idx - i; 
    }

    for (i = l+1; i < r; i++) { 
        res[i] = MIN(res[i], tmp[i]);
    }

    *returnSize = len;
    return res;
}








int main()
{
	int *dis, len;
	char s[] = "aaba", c = 'b';
	dis = shortestToChar(s, c, &len);
	for (int i = 0; i < len; i++) 
		printf("%d ",dis[i]);
	return 0;
}






